\documentclass{article}
\usepackage{xltxtra}
\usepackage{ctex}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{geometry}
\usepackage{booktabs}
\usepackage{graphicx}
\usepackage{float}
\usepackage{geometry}
\usepackage{booktabs}

\makeatother
\geometry{a4paper,top=1.5cm,bottom=1.5cm}

\title{Programming assignments for Section 1}
\author{张皓祥 \\ 3200102536 强基数学2001}
\date{}

\begin{document}
\maketitle

% Question A, 关于 C++ 类的构建
\noindent \textbf{A. Implement the bisection method, Newton's method and the secant method in a C++ package.}

在 $EquationSolver.h$ 中，定义了两个抽象类用以规范定义的仿函数和求解器。

其中， $Function$ 类中把操作符()重载为一个纯虚函数，规定了所有派生类重载()这一操作符的规范。
同时，该虚类还定义了求导数的虚函数，该函数在派生类中可以实体化应用。

此外，另一个抽象类 $EquationSolver$ 则定义了一个纯虚函数 $solve()$，用该函数规范了所有派生类
的求解函数的格式和接口。

具体而言，该函数库实现了二分法求解零点(bisection method)，牛顿迭代法(Newton's method) 和
割线法(secant method) 三种求解函数零点近似解的方法，并且封装在三个相应的类中，调用了统一的
求解函数接口 $double \quad solve()$.
\bigskip

% Question B, test for bisection method.
\noindent \textbf{B.  Test the bisection method on the following function and intervials.}

\noindent $\bullet \quad x^{-1}-\tan x \quad \mbox{on} \quad [0,\frac{\pi}{2}].$

把对应函数通过仿函数定义为一个函数类，运用 $Bisection$ 类进行求解。为了避免函数在0或
$\frac{\pi}{2}$处无意义，实际计算时区间变量赋予一个很小的偏差量，得到近似解为$x=0.860334$，
此时回代函数，函数计算结果为 $-1.36047e-06$ 和0误差很小，可以认为得到的为近似零点。
\bigskip

\noindent $\bullet \quad x^{-1}-2^x \quad \mbox{on} \quad [0,1].$

为了防止函数在0处无意义，对区间左端点做一个很小的偏移量，迭代计算得到近似解为 $x=0.641186$,
回代函数，计算结果为$7.39659e-07$ 和0误差很小，可以认为得到的为近似零点。
\bigskip

\noindent $\bullet \quad 2^{-x}+e^x+2\cos x -6 \quad \mbox{on} \quad [1,3].$

迭代计算得到近似解为 $x=1.82938$, 回代函数，计算结果为 $-2.89365e-06$ 很接近0，
可以认为得到的为近似零点。
\bigskip

\noindent $\bullet \quad (x^3+4x^2+3x+5)/(2x^3-9x^2+18x-2) \quad \mbox{on} \quad [0,4].$

迭代计算得到近似解为 $x=0.117877$，然而回代函数计算结果为 $2.24202e+09$ 远大于0.
为了探究其原因，可以对该函数进行作图分析，如下：
\begin{figure}[H]
    \centering
    \includegraphics[scale=0.4]{./figure/B1.png} \label{B1}
\end{figure}    
显然，此时对于对应的函数，其分子部分 $y_1(x)=x^3+4x^2+3x+5$ 在区间 $[0,4]$ 上没有零点，
并且恒大于0，而对于分母部分 $y_2(x)=2x^3-9x^2+18x-2$，其在区间 $[0,4]$ 上单调递增且在0附近
具有零点，因此对于总函数 $y = \frac{y_1}{y_2}$，其在0的一个邻域内小于0，在另一部分大于0.
假设分界点为 $\alpha$，则在$\alpha$附近函数变号，而根据 Bisection method 的收敛条件，在
给定区间上，近似解会趋近于$\alpha$，而实际上在这点给定函数并无意义，并且在该点有$y_2(\alpha)=0$，
因此在该点附近函数会趋向于$\infty$，因此得到的“近似解”实际上计算得到的函数值与0距离很大。
\bigskip

% Question C, test for Newton's method.
\noindent \textbf{C. Test the Newton's method by solving $x=\tan x$.}

使用继承的方法构造一个 $Function$ 类的派生类 $func$, 其为一个仿函数类可以计算 $y(x)=x-\tan x$
及其函数，可以先使用一个图像对该函数零点位置有一个直观印象($y=\tan x$断点处在画图时连了起来)：
\begin{figure}[H]
    \centering
    \includegraphics[scale=0.4]{./figure/C1.png} \label{C1}
\end{figure}

取定初值为4.5， 应用 Newton's Method，可以计算得到该函数在4.5附近的根$x_1=4.49341$，
代入仿函数类中验证，可以得到$y(x_1)=3.45349e-09$和0很接近，可以认为得到的为近似零点。
再取定初值为7.7，应用 Newton's Method,计算得到7.7附近的根为$x_2=7.72525$，代入仿函数类
中验证，得到$y(x_2)=6.48494e-09$和0同样很接近，可以认为得到的为近似零点。
\bigskip

% Question D, test for secant method.
\noindent \textbf{D. Test the secant method by the following functions.}

\noindent $\bullet \quad \sin(x/2)-1 \quad \mbox{with} \quad x_0=0,x_1=\frac{\pi}{2}$

构造一个仿函数，应用 secant method 去计算这一个函数零点，取定初值为 $x_0=0,x_1=\frac{\pi}{2}$,
得到近似解为$x=3.12242$，很接近真解$\pi$，该方法确实能求得近似解。更改初值为 $x_0=4.5\pi,x_1=4.7\pi$，
得到解为$x=15.6959\approx 5\pi$很接近真解，即选定不同初值会得到不同的近似解。探究原因，
是$sin(x/2)$这个函数为周期函数，对题中函数可以做出函数图像如下：
\begin{figure}[H]
    \centering
    \includegraphics[scale=0.4]{./figure/D1.png} \label{D1}
\end{figure}

\noindent $\bullet \quad e^x-\tan x \quad \mbox{with} \quad x_0=1,x_1=1.4$

应用 secant method 去计算，取定初值 $x_0=1,x_1=1.4$，得到近似解为$x=1.30633$，回代函数
得到函数值为$-2.84341e-08$和0很接近，可以认为是近似解。更改初值为$x_0=-3.5,x_1=-3$，得到
近似解为$x=-3.09641$，回代函数得到函数值为$-1.35575e-09$同样很接近0，亦可以认为是近似解。
对于该函数，同样可以知道该函数应该有不同的零点。其原因在于$\tan x$是一个周期函数，且在每个
周期内取值都遍历整个实数域$\mathbb{R}$，在一定区域内，该函数图像如下：
\begin{figure}[H]
    \centering
    \includegraphics[scale=0.4]{./figure/D2.png}  \label{D2}
\end{figure}

\noindent $\bullet \quad x^3-12x^2+3x+1 \quad \mbox{with} \quad x_0=0,x_1=-0.5$

应用 secant method 去计算，取定初值 $x_0=1,x_1=1.4$，得到近似解为$x=-0.188685$，回代函数
得到函数值为$2.16709e-08$和0很接近，可以认为是近似解。更改初值为$x_0=0.8,x_1=1$，得到
近似解为$x=0.451543$，回代函数得到函数值为$-3.61216e-09$同样很接近0，亦可以认为是近似解。
同样可以发现该函数有不同的零点，其原因在于该函数为三次函数，可数学推导得该函数两个极值点异号，
故其应该具有三个不同的实根，其函数图像如下
\begin{figure}[H]
    \centering
    \includegraphics[scale=0.4]{./figure/D3.png} \label{D3}
\end{figure}

% Question E, find the depth of the water
\noindent \textbf{E. Find the depth of water by each of the three implementations.}

定义一个仿函数用于计算$f(h)=L[0.5\pi r^2-r^2\arcsin\frac{h}{r}-h(r^2-h^2)^{\frac{1}{2}}]-V$，
则取定了$L,r,V$的值以后，该函数的零点对应数值即为所求的水深(depth).

取定$L=10, r=1, V=12.4$，分别使用 Bisection method, Newton's method, Secant method 三种
求解器对该函数进行求解，可以得到误差在$0.01ft$内的结果分别如下：
\bigskip
\\
\resizebox{\columnwidth}{!}{\begin{tabular}{ccc}
    \toprule[1.5pt]
    \makebox[0.3\textwidth][c]{Method} & 
    \makebox[0.4\textwidth][c]{depth $h$ / $ft$} &
    \makebox[0.3\textwidth][c]{error $\Delta V(h)$ / $ft^3$} \\
    \midrule[0.75pt]
    Bisection & 0.164146 & 0.039844 \\
    Newton & 0.166162 & 8.91174e-05 \\
    Secant & 0.166166 & -1.77886e-06 \\
    \bottomrule[1.5pt]
\end{tabular}}

\bigskip
再验证求得的根和真实值误差，以 Newton's method 求得的解$h=0.166162ft$为例，做偏移0.01
再求函数值得 $f(h-0.01)=0.197474>0,f(h+0.01)=-0.196959<0$，由零点存在定理，该方程的
真实解在区间$[h-0.01,h+0.01]$中，即实际水深(depth)和计算值误差在$0.01ft$以内。
\bigskip

% Question F, find the maximum angle
\noindent \textbf{F. Find the maximum angle $\alpha$.}

首先构造一个可以把角度换为弧度的函数 $double AnglePi(double x)$ 用于把给定角度值转化为计算时
使用的弧度运算。然后构造一个仿函数 $Fun$，其在输入对应参数 $l,h,D,\beta_1$ 取值后可以求出对应的
参数值 $A,B,C,E$.给定任意角度$\theta$，该函数会先把角度转化为弧度，再计算函数值
$f(\theta)=A\sin\theta\cos\theta + B\sin^2\theta - C\cos\theta - E\sin\theta$ 的值。
目标需要求得的最大角度$\alpha$即为函数$f(\theta)$的零点。
\bigskip

% Topic (a)
\noindent \textbf{(a) Use Newton's method to verify $\alpha\approx 33^{\circ}.$}

要验证结论，只需要把对应参数 $l=89,h=49,D=55,\beta_1=11.5^{\circ}$ 代入仿函数中并且应用 
Newton's method 求解器求解出对应根，并与猜测值比较即可。代入相关参数，可以计算得到近似解为 
$\alpha_1=32.9714^{\circ}$.把这个值回代至函数得$f(\alpha_1)=-0.000732175$十分靠近0，因此
可以认为得到的为零点。而这个解保留两位有效数字得到的结果即为$33^{\circ}$，故(a)中的命题成立，
证毕！
\bigskip

% Topic (b)
\noindent \textbf{(b) Use Newwton's method to find $\alpha$ with initial guess 
$33^{\circ}$ for $D = 30$ in.}

按照题目要求选定$D=30$以及初值$x_0=33^{\circ}$，由于取定$33^{\circ}$时迭代法计算超出精度范围，
做一个微小扰动为取定初值$33.001^{\circ}$，此时计算得到的解为$\alpha_2=33.1691^{\circ}$.回代
该值得$f(\alpha_2)=0.000146708$约为0，可以认为该角度值为对应零点。
\bigskip

% Topic (c)
\noindent \textbf{(c) Use the secant method to find $\alpha$ and discuss why there
will be different result if the initial value is too far away from $33^{\circ}$.}

把参数取定为和(a)相同，应用 Secant method 去寻找目标角度$\alpha$.
\begin{itemize}
    \item 取定初值为 $x_0=85^{\circ},x_1=80^{\circ}$,求解得到解为
          $\alpha_3=-371.086^{\circ}$.回代函数得$f(\alpha_3)=-0.474391$约为0，此时
          $\alpha_3$亦为一个近似的零点。
    \item 取定初值为 $x_0=88^{\circ},x_1=86^{\circ}$,求解得到解为
          $\alpha_4=--95253^{\circ}$.回代函数得$f(\alpha_4)=4.76118e-05$约为0，此时
          $\alpha_4$亦为一个近似的零点。
\end{itemize}
如上，选取两组远离$33^{\circ}$的初值，利用 secant method 得到的近似零点会远远偏离$33^{\circ}$.

\noindent \textbf{原因分析：}

给定参数，在$0^{\circ}-90^{\circ}$范围内做出 $\theta - f$ 的图像如下图：
\begin{figure}[H]
    \centering
    \includegraphics[scale=0.4]{./figure/F1.png} \label{F1}
\end{figure}
分析图像，在给定范围内，对应函数仅有一个零点$33^{\circ}$，同时在33附近，给定函数$y=f(x)$单调
递增并且在一个小邻域内为凹函数，因此在33的一定邻域内使用 Newton's method 和 Secant method 来
求解对应的零点是可以收敛到一个给定区间内的真实解的。

放到给定区间，并且作出两次改变初值对应的第一条割线如下图：
\begin{figure}[H]
    \centering
    \includegraphics[scale=0.4]{./figure/F2.png} \label{F2}
\end{figure}
通过$y=f(x)$在更大范围内的图像可以知道，实际上由于给定函数中存在的三角函数，该函数在不断震荡，
有多个零点。如果把初值取在了$f(x)$的极大值点附近并且离得比较近，由于在这部分函数为凸函数，
给定的割线斜率绝对值会十分小，以至于其零点远远超出了合理的求解范围$0^{\circ}-90^{\circ}$.
在不断迭代后，最后零点会在远离初值的一个点附近收敛到一个其他零点，而这样的零点会远远偏离于
$33^{\circ}$.

\end{document}